32. Sliding Blocks Puzzle 1

INSTRUCTOR NOTE:

h2 is always greater than h1 as each misplaced block must always need to move at least a distance of 1, but that distance could be greater than 1.

Why does h2 expand fewer nodes than h1?

As Peter says, h2 is always greater than or equal to h1. To see why this should expand fewer paths, let's imagine a heuristic h3 that always had the exact cost at every node. This heuristic would naturally expand the least number of nodes, as it would know the actual best path to take at each step.

On the other hand, imagine a heuristic h4 that was always 0. This heuristic would expand the most number of nodes of all possible heuristics, as it would have essentially no knowledge of estimated "distance" to the goal, and therefore be more similar to Uniform Cost search.

You can see then that a heuristic that is strictly greater than or equal to another one (assuming it is still admissible!) gets us closer to the perfect heuristic and thereby expands at least the same number of nodes or fewer.